import java.util.ArrayList;
import java.util.List;

public class ConvertBSTToGreaterTree {
    /**
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
     * 使每个节点 node的新值等于原树中大于或等于node.val的值之和。
     * 提醒一下，二叉搜索树满足下列约束条件：
     * 节点的左子树仅包含键 小于 节点键的节点。
     * 节点的右子树仅包含键 大于 节点键的节点。
     * 左右子树也必须是二叉搜索树。
     * 链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
     * @param root
     * @return
     */
    List<TreeNode> nodeList = new ArrayList<>();
    public TreeNode convertBST(TreeNode root) {
        inorder(root);
        int temp_sum =0;
        for (int i=nodeList.size()-1;i>=0;i++){
            temp_sum+=nodeList.get(i).val;
            nodeList.get(i).val = temp_sum;
        }
        return root;

    }

    public void inorder(TreeNode treeNode){
        if (treeNode==null)
            return;
        inorder(treeNode.left);
        nodeList.add(treeNode);
        inorder(treeNode.right);
    }
}
